#include <iostream>
#include <vector>
using namespace std;

class Solution
{
public:
    int maxProfit(int k, vector<int> &prices)
    {
        vector<vector<int>> dp(prices.size(), vector<int>(k * 2, INT_MIN)); // 0,1,2,3..k op times
        dp[0][0] = -prices[0];
        for (int i = 1; i < prices.size(); i++)
        {
            // op0
            dp[i][0] = max(dp[i - 1][0], -prices[i]);
            // op1
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
            for (int j = 2; j < k * 2; j += 2)
            {
                // op2n
                if (dp[i - 1][j-1] != INT_MIN)
                    dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] - prices[i]);
                // op2n+1
                if (dp[i - 1][j] != INT_MIN)
                    dp[i][j + 1] = max(dp[i - 1][j + 1], dp[i - 1][j] + prices[i]);
            }
        }
        int max = *max_element(dp[prices.size() - 1].begin(), dp[prices.size() - 1].end());
        return max < 0 ? 0 : max;
    }
};

int main()
{
    cout << "Code188" << endl;
    Solution s;
    vector<int> prices = {3, 2, 6, 5, 0, 3};
    cout << s.maxProfit(2, prices) << endl;
    return 0;
}